0623. 在二叉树中增加一行【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - BFS

1. 📝 题目描述

• leetcode

给定一个二叉树的根 root 和两个整数 val 和 depth，在给定的深度 depth 处添加一个值为 val 的节点行。

注意，根节点 root 位于深度 1。

加法规则如下:

• 给定整数 depth，对于深度为 depth - 1 的每个非空树节点 cur，创建两个值为 val 的树节点作为 cur 的左子树根和右子树根。
• cur 原来的左子树应该是新的左子树根的左子树。
• cur 原来的右子树应该是新的右子树根的右子树。
• 如果 depth == 1 意味着 depth - 1 根本没有深度，那么创建一个树节点，值 val 作为整个原始树的新根，而原始树就是新根的左子树。

---

示例 1：

输入: root = [4,2,6,3,1,5], val = 1, depth = 2
输出: [4,1,1,2,null,null,6,3,1,5]

示例 2：

输入: root = [4,2,null,3,1], val = 1, depth = 3
输出:  [4,2,null,1,1,3,null,null,1]

---

提示：

• 节点数在 [1, 10^4] 范围内
• 树的深度在 [1, 10^4]范围内
• -100 <= Node.val <= 100
• -10^5 <= val <= 10^5
• 1 <= depth <= the depth of tree + 1

2. 🎯 s.1 - BFS

c

struct TreeNode* addOneRow(struct TreeNode* root, int val, int depth) {
    if (depth == 1) {
        struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        node->val = val; node->left = root; node->right = NULL;
        return node;
    }
    struct TreeNode* queue[10000];
    int head = 0, tail = 0;
    queue[tail++] = root;
    for (int d = 1; d < depth - 1; d++) {
        int size = tail - head;
        for (int i = 0; i < size; i++) {
            struct TreeNode* cur = queue[head++];
            if (cur->left) queue[tail++] = cur->left;
            if (cur->right) queue[tail++] = cur->right;
        }
    }
    for (int i = head; i < tail; i++) {
        struct TreeNode* cur = queue[i];
        struct TreeNode* nl = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        struct TreeNode* nr = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        nl->val = val; nl->left = cur->left; nl->right = NULL;
        nr->val = val; nr->left = NULL; nr->right = cur->right;
        cur->left = nl; cur->right = nr;
    }
    return root;
}

js

/**
 * @param {TreeNode} root
 * @param {number} val
 * @param {number} depth
 * @return {TreeNode}
 */
var addOneRow = function (root, val, depth) {
  if (depth === 1) {
    const node = new TreeNode(val)
    node.left = root
    return node
  }
  const queue = [root]
  for (let d = 1; d < depth - 1; d++) {
    const size = queue.length
    for (let i = 0; i < size; i++) {
      const node = queue.shift()
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }
  }
  for (const node of queue) {
    const newLeft = new TreeNode(val)
    const newRight = new TreeNode(val)
    newLeft.left = node.left
    newRight.right = node.right
    node.left = newLeft
    node.right = newRight
  }
  return root
}

py

class Solution:
    def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:
        if depth == 1:
            node = TreeNode(val)
            node.left = root
            return node
        queue = deque([root])
        for _ in range(depth - 2):
            for _ in range(len(queue)):
                cur = queue.popleft()
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
        for cur in queue:
            nl, nr = TreeNode(val), TreeNode(val)
            nl.left, nr.right = cur.left, cur.right
            cur.left, cur.right = nl, nr
        return root

• 时间复杂度：$O(n)$，其中 n 是节点数
• 空间复杂度：$O(n)$

算法思路：

• BFS 遍历到第 depth - 1 层
• 对该层每个节点，创建两个值为 val 的新节点插入为左右子节点
• 原左子树挂到新左节点的左子树，原右子树挂到新右节点的右子树